package com.example.leetcode.prcatice;

/**
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 */
public class Test64 {

    public int minPathSum(int[][] grid) {
        int len = grid.length;
        int len1 = grid[0].length;
        int[][] r = new int[len][len1];
        r[0][0] = grid[0][0];
        for(int i =1;i<len;i++){
            r[i][0] = r[i-1][0] + grid[i][0];
        }
        for (int j = 1;j<len1;j++){
            r[0][j] = r[0][j-1] + grid[0][j];
        }
        for (int i = 1; i<len;i++){
            for (int j = 1;j<len1;j++){
                r[i][j] = grid[i][j] + Math.min(r[i-1][j],r[i][j-1]);
            }
        }
        return r[len-1][len1-1];
    }
}
